package com.dy.分类.链表.合并k个排序链表;

import java.util.Comparator;
import java.util.LinkedList;
import java.util.PriorityQueue;

/**
 * 合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
 * <p>
 * 示例:
 * <p>
 * 输入:
 * [
 * 1->4->5,
 * 1->3->4,
 * 2->6
 * ]
 * 输出: 1->1->2->3->4->4->5->6
 */
class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}

//思路 用最小堆，k 将头加进去，每次输出头部，再将该链表的下一个加进来
public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> pq = new PriorityQueue<>(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o1.val - o2.val;
            }
        });
        for (int i = 0; i < lists.length; i++) {
            if (lists[i] != null) {
                pq.add(lists[i]);
            }
        }
        ListNode res = new ListNode(1);
        ListNode p = res;
        while (!pq.isEmpty()) {
            ListNode min = pq.poll();
            p.next = min;
            p = p.next;
            if (min.next != null) pq.add(min.next);
        }
        return res.next;
    }

    public ListNode mergeKLists2(ListNode[] lists) {
        if (lists.length == 0) {
            return null;

        }
        if (lists.length == 1) {
            return lists[0];
        }
        if (lists.length == 2) {
            return merge(lists[0], lists[1]);
        }
        int mid = lists.length / 2;
        ListNode[] before = new ListNode[mid];
        ListNode[] after = new ListNode[lists.length - mid];
        for (int i = 0; i < mid; i++) {
            before[i] = lists[i];
        }
        for (int i = mid; i < lists.length; i++) {
            after[i-mid] = lists[i];
        }
        ListNode left = mergeKLists2(before);
        ListNode right = mergeKLists2(after);
        return merge(left, right);
    }

    public ListNode merge(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        ListNode res;
        if (l1.val <= l2.val) {
            res = l1;
            res.next = merge(l1.next, l2);
        } else {
            res = l2;
            res.next = merge(l1, l2.next);
        }
        return res;
    }
}
